//
// Created by LovingYoung on 11/1/2015.
//

#ifndef HANOI_HANOI_H
#define HANOI_HANOI_H

#include <iostream>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include "status.h"

using namespace std;

namespace liuyang {

    ofstream fout("data.out");

    class Hanoi {
    public:

        //Construtor
        Hanoi() : level(5), preLevel(0) {};

        Hanoi(int m_level) : level(m_level), preLevel(0) { };

        //interface
        vector<vector<int> > getShortestPath() {
            if (preLevel != level) {
                searchPath = search();
                shortestPath = shortest();
                preLevel = level;
            }
            return shortestPath;
        }

        vector<vector<int> > getSearchPath() {
            if (preLevel != level) {
                searchPath = search();
                shortestPath = shortest();
                preLevel = level;
            }
            return searchPath;
        }

    private:
        int level;
        int preLevel;
        liuyang::status * root = NULL;

        vector<vector<int> > searchPath;
        vector<vector<int> > shortestPath;

        //the path of search
        vector<vector<int> > search() {
            set<liuyang::status> mySet;
            queue<liuyang::status *> myQueue;

            vector<int> tempVector;
            vector<vector<int> > * tempPath = new vector<vector<int> >;
            vector<vector<int> > & temp = *tempPath;

            vector<int> every(level, 0);

            liuyang::status * sta = new liuyang::status(level, every);

            myQueue.push(sta);

            liuyang::status * pre = NULL;

            while(!myQueue.empty() && !myQueue.front()->isComplete()){
                liuyang::status * origin= myQueue.front();
                vector<int> origin_v = origin->getStatus();
                myQueue.pop();
                if(mySet.find(*origin) != mySet.end())
                    continue;
                else mySet.insert(*origin);

                //find parent:
                liuyang::status * parent = origin->getParent();
                liuyang::status * all = NULL;
                if(parent != pre){
                    int flag = 0;
                    liuyang::status * tempPointer = parent;
                    while(tempPointer != NULL && !flag){
                        liuyang::status * tempPointer2 = pre;
                        while(tempPointer2 != NULL && !flag){
                            if(tempPointer == tempPointer2){
                                all = tempPointer;
                                flag = 1;
                            }
                            tempPointer2 = tempPointer2->getParent();
                        }
                        tempPointer = tempPointer->getParent();
                    }
                    vector<vector<int> > parent_v;
                    tempPointer = pre -> getParent();
                    while(tempPointer != all) {
                        tempVector = tempPointer->getStatus();
                        tempVector.push_back(0);
                        parent_v.push_back(tempVector);
                        tempPointer = tempPointer ->getParent();
                    }

                    vector<vector<int> > in_v;
                    while(parent != all){
                        tempVector = parent->getStatus();
                        tempVector.push_back(0);
                        in_v.push_back(tempVector);
                        parent = parent->getParent();
                    }

                    temp.insert(temp.end(),parent_v.begin(), parent_v.end());
                    tempVector = all->getStatus();
                    tempVector.push_back(0);
                    temp.push_back(tempVector);
                    temp.insert(temp.end(),in_v.rbegin(), in_v.rend());
                }

                tempVector = origin_v;
                tempVector.push_back(1);
                temp.push_back(tempVector);
                pre = origin;
                //generate 3 situations after.
                int index[3] = {10000,10000,10000};
                for(int i = level - 1; i >= 0; i--){
                    if(i < index[origin_v[i]]) index[origin_v[i]] = i;
                }

                int lowest = 0;
                for(int i = 0; i < 3; i++){
                    if(index[i] == 0) lowest = i;
                }

                int o1 = (lowest + 1) % 3;
                int o2 = (lowest + 2) % 3;

                int sonNum;

                if(index[o1] == 10000 && index[o2] == 10000){
                    sonNum = 2;
                    origin_v[index[lowest]] = o1;
                    liuyang::status *st = new liuyang::status(origin->getLevel(), origin_v, origin);
                    st->addSteps();
                    myQueue.push(st);
                    origin_v[index[lowest]] = 0;

                    origin_v[lowest] = o2;
                    liuyang::status *st2 = new liuyang::status(origin->getLevel(), origin_v, origin);
                    st2->addSteps();
                    myQueue.push(st2);
                    origin_v[index[lowest]] = 0;
                }

                else{
                    sonNum = 3;
                    int tempO;

                    int maxO = index[o1] > index[o2] ? o1 : o2;
                    int minO = index[o2] > index[o1] ? o1 : o2;

                    tempO = origin_v[index[lowest]];
                    origin_v[index[lowest]] = minO;
                    liuyang::status * st1 = new liuyang::status(origin->getLevel(), origin_v, origin);
                    st1->addSteps();
                    myQueue.push(st1);
                    origin_v[index[lowest]] = tempO;

                    tempO = origin_v[index[lowest]];
                    origin_v[index[lowest]] = maxO;
                    liuyang::status * st2 = new liuyang::status(origin->getLevel(), origin_v, origin);
                    st2->addSteps();
                    myQueue.push(st2);
                    origin_v[index[lowest]] = tempO;

                    tempO = origin_v[index[minO]];
                    origin_v[index[minO]] = maxO;
                    liuyang::status * st3 = new liuyang::status(origin->getLevel(), origin_v, origin);
                    st3->addSteps();
                    myQueue.push(st3);
                    origin_v[index[minO]] = tempO;
                }
            }
            this->root = myQueue.front();
            tempVector = myQueue.front()->getStatus();
            tempVector.push_back(1);
            temp.push_back(tempVector);

//            for(int i = 0; i < temp.size(); i++){
//                for(int j = 0; j < temp[i].size() ; j++){
//                    fout << temp[i][j] << " ";
//                }
//                fout << endl;
//            }

            return temp;
        }

        //the shortest path of problem
        vector<vector<int> > shortest() {
            vector<vector<int> > * tempPath = new vector<vector<int> >;
            vector<vector<int> > & temp = *tempPath;
            vector<vector<int> > * reverse = new vector<vector<int> >;
            liuyang::status * tempPointer = root;
            while(tempPointer != NULL){
                vector<int> temp = tempPointer->getStatus();
                reverse->push_back(temp);
                tempPointer = tempPointer ->getParent();
            }
            tempPath->insert(tempPath->end(), reverse->rbegin(), reverse->rend());
            for(int i = 0; i < temp.size(); i++){
                for(int j = 0; j < temp[i].size() ; j++){
                    fout << temp[i][j] << " ";
                }
                fout << endl;
            }
            return *tempPath;
        }
    };
}

#endif
